package problem376;

//376.摆动序列
//https://leetcode.cn/problems/wiggle-subsequence/
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = 1;
        int ret = 1;
        for(int i = 1; i<n; i++) {
            for(int j = i-1; j>=0; j--) {
                if(nums[i]-nums[j] > 0) {
                    f[i] = Math.max(g[j]+1, f[i]);
                }else if(nums[i] - nums[j] < 0) {
                    g[i] = Math.max(f[j]+1, g[i]);
                }
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
}

/*
f[i]:以第i个数字为结尾, 且nums[i]-nums[i-1] > 0 的最长摆动子序列的长度
g[i]:以第i个数字为结尾, 且nums[i]-nums[i-1] < 0 的最长摆动子序列的长度
*/